package review.linkedList;

public class SinglyLinkedListSentinel<E> implements ILinkedList<E> {
    Node head = new Node(-1, null);

    @Override
    public boolean addFirst(E val) {
        head.next = new Node(val, head.next);
        return true;
    }

    @Override
    public boolean addLast(E val) { // 没加哨兵之前 需要考虑头结点为空 避免空指针
        Node p = head;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new Node(val, null);
        return true;
    }

    @Override
    public boolean insert(int index, E val) {
        if(index<0){
            throw new IndexOutOfBoundsException("Index must be non-negative");
        }
        Node prev = head;
        int i = -1;
        while (prev != null && i != index - 1) {
            i++;
            prev = prev.next;
        }
        if(prev == null){
            throw new IndexOutOfBoundsException("index["+index+"] out of bounds");
        }
        prev.next = new Node(val,prev.next);
        return true;
    }

    @Override
    public E get(int index) {
        if(index < 0){
            throw new IndexOutOfBoundsException("Index must be non-negative");
        }
        Node p = head.next;
        if(p == null){
            throw new IndexOutOfBoundsException("list is empty");
        }
        int i = 0;
        while(p!=null && i!=index){
            i++;
            p = p.next;
        }
        if(p == null){
            throw new IndexOutOfBoundsException("Index["+index+"] out of bounds");
        }
        return null;
    }

    @Override
    public E removeFirst() {
        if(head.next == null){
            throw new IndexOutOfBoundsException("list is empty");
        }
        E val = (E) head.next.val;
        head.next = head.next.next;
        return val;
    }

    @Override
    public E remove(int index) {
        if(index < 0){
            throw new IndexOutOfBoundsException("Index must be non-negative");
        }
        Node prev = head;
        int i =-1;
        while(prev!=null && i!=index-1){
            i++;
            prev = prev.next;
        }
        if(prev == null || prev.next == null){
            throw new IndexOutOfBoundsException("Index ["+index+"] out of bounds");
        }
        E val = (E) prev.next.val;
        prev.next = prev.next.next;
        return val;
    }

    @Override
    public Node findNode(int index) {
        Node p = head.next;
        int i = 0;
        while(p!=null && i!=index){
            i++;
            p = p.next;
        }
        return p;
    }
}
